public class Test {
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) {
            return root;
        }
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.val == 0 && root.left == null && root.right == null) {
            return null;
        }
        return root;
    }
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    int dfs(TreeNode root, int sum) {
        sum = sum * 10 + root.val;
        int count = 0;
        if(root.left != null) count += dfs(root.left, sum);
        if(root.right != null) count += dfs(root.right, sum);
        return count == 0 ? sum : count;
    }
    public boolean evaluateTree(TreeNode root) {
        if(root.val == 1)
            return true;
        else if(root.val == 0)
            return false;

        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        return root.val == 2 ? left | right : left & right;
    }
    public static void main(String[] args) {

    }
    long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root.left != null && !isValidBST(root.left))
            return false;
        if(root.val > prev) {
            prev = root.val;
        } else {
            return false;
        }
        if(root.right != null && !isValidBST(root.right))
            return false;
        return true;
    }
    int prev = 0;
    int count = 0;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        return dfs(root);
    }
    int dfs(TreeNode root) {
        if(count == 0) {
            return prev;
        }
        if(root.left != null) {
            dfs(root.left);
        }
        if(count == 0) {
            return prev;
        } else {
            prev = root.val;
            count--;
        }
        if(root.right != null) {
            dfs(root.right);
        }
        return prev;
    }
    List<String> ans = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        return dfs(root, new StringBuffer());
    }
    List<String> dfs(TreeNode root, StringBuffer _path) {
        StringBuffer path = new StringBuffer(_path);
        path.append(root.val);
        if(root.left == null && root.right == null) {
            ans.add(path.toString());
            return ans;
        }
        path.append("->");
        if(root.left != null) {
            dfs(root.left,path);
        }
        if(root.right != null) {
            dfs(root.right,path);
        }
        return ans;
    }
}
